package com.gitee.ywj1352.算法.week05;


import java.util.*;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
 * <p>
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <p>
 * <p>
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 */
public class 零钱兑换 {


    /**
     * 1， BFS 递归树 最小的一层
     * 2， DP 使用
     */

    public int coinChange(int[] coins, int amount) {


        return 2;
    }


    static int ans = 0;

    public static int numDecodings(String s) {
        hepler(s);
        return ans;
    }

    public static void hepler(String s) {
        if (s.length() == 0) {
            ans++;
            return;
        }
        if (s.length() > 1) {
            String s2 = s.substring(0, 2);
            if (!s2.startsWith("0") && Integer.parseInt(s2) <= 26) {
                hepler(s.substring(2));
            }
        }
        if (!s.startsWith("0")) {
            hepler(s.substring(1));
        }
    }

    int max = Integer.MAX_VALUE;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int lianxu = 0;
        Deque<String> deque = new LinkedList<>();
        deque.addLast(beginWord);
        boolean[] marked = new boolean[wordList.size() + 1];
        while (!deque.isEmpty()) {
            int size = deque.size();
            lianxu++;
            for (int i = 0; i < size; i++) {
                String w = deque.removeFirst();
                for (String s : wordList) {
                    if (marked[i]) continue;
                    if (diff(s.toCharArray(), w.toCharArray())) {
                        if (w.equals(endWord)) return lianxu;
                        deque.addLast(s);
                        marked[i] = true;
                    }
                }
            }

        }
        return lianxu;
    }


    boolean diff(char[] a, char[] b) {
        if (a.length != b.length) return false;
        int diff = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) diff++;
        }

        return diff == 1;
    }

    public static int compress(char[] chars) {
        char pre = chars[0];
        int r = 0, i = 0, jin = 0;
        while (true) {
            while (r < chars.length && pre == chars[r]) {
                if (r != i) {
                    chars[r] = '#';
                }
                r++;
            }
            if (r - i > 1) {
                char[] chars1 = String.valueOf(r - i).toCharArray();
                for (int j = 0; j < chars1.length; j++) {
                    chars[i + j + 1] = chars1[j];
                }
            }
            if (r >= chars.length) break;
            pre = chars[r];
            i = r;
        }
        System.out.println(Arrays.toString(chars));
        int max = 0;
        for (int j = 0; j < chars.length; j++) {
            while (j < chars.length && chars[j] == '#') {
                jin++;
                j++;
            }
            //System.out.println(i - jin);
            if (j < chars.length && chars[j] != '#') {
                chars[j - jin] = chars[j];
                max = Math.max(max, j - jin);
            }
        }
        return max;

    }


    public static void main(String[] args) {
        char[] chars = "oo".toCharArray();
        int i = compress(chars);
        System.out.println(i);
        System.out.println(Arrays.toString(chars));
    }

}
